// 实现int sqrt(int x)函数，计算并返回x的平方根（只保留整数部分），其中x是非负整数

// 思路：求解的是x开方的整数部分，所以我们可以从0-x的范围内遍历，找到k^2 <= x的最大结果
// 采用二分查找的方法

function mySqrt(x) {
    let left = 0
    let right = x
    let ans = -1
    while (left < right) {
        let mid = Math.floor((right - left) / 2) + left
        if (mid * mid <= x) {
            ans = mid
            left = mid + 1
        } else {
            right = mid
        }
    }
    return ans
}

// 时间复杂度：O(logn)
// 空间复杂度：O(1)

console.log(mySqrt(4))